Now that we understand the 'expanding frontier' analogy, let's begin a concrete, step-by-step walkthrough of Prim's algorithm using our example graph.

  • The first step is initialization. We can start from any arbitrary vertex; for this example, we will start at vertex A.
  • The choice of start node does not change the total weight of the final MST, only the order of edges chosen.
  • We use a set to store vertices already in our MST (the "settled territory").
  • We use a priority queue to store potential edges that cross from our settled territory to the unexplored frontier.
  • The priority queue is ordered by edge weight, allowing us to always find the cheapest "bridge" to cross next.
  • We initialize by adding vertex A to the MST set, then add all of its connecting edges to the priority queue.
Python: Prim's Initialization
1import heapq
2
3# Adjacency list representation of Shared_Graph
4graph = {
5    'A': {'B': 4, 'C': 3},
6    'B': {'A': 4, 'C': 1, 'D': 5},
7    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 6},
8    'D': {'B': 5, 'C': 2, 'E': 8, 'F': 7},
9    'E': {'C': 6, 'D': 8, 'F': 9},
10    'F': {'D': 7, 'E': 9}
11}
12
13# 1. Initialization
14mst_vertices = set()
15priority_queue = [] # Min-heap of (weight, u, v)
16start_vertex = 'A'
17
18# 2. Add start vertex to MST set
19mst_vertices.add(start_vertex)
20
21# 3. Add all its edges to the priority queue
22for neighbor, weight in graph[start_vertex].items():
23    heapq.heappush(priority_queue, (weight, start_vertex, neighbor))
24
25print(f"MST Vertices: {mst_vertices}")
26print(f"Priority Queue: {priority_queue}")